package com.bascker.algorithm.practice.double_point.next_permutation;

public class Solution {

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }

        int i = n - 2;
        int j = n - 1;
        int k = n - 1;

        // 从后往前找到一个第一个「相邻升序」的元素对
        while (i >= 0 && nums[i] >= nums[j]) {
            i --;
            j --;
        }

        // 若不是最后一个队列, 则找到大数和小数
        if (i >= 0) {
            // 在 [j,end) 从后向前 查找第一个满足 nums[i] < nums[k] 的 k
            // nums[i]就是小数, nums[k] 就是尽可能小的大数
            while (nums[i] >= nums[k]) {
                k --;
            }

            // 元素交换
            int temp = nums[k];
            nums[k] = nums[i];
            nums[i] = temp;
        }

        // reverse nums[j:end], 这时候 nums[j:end] 一定是降序的，因此要改为升序  ==> 若当前数列本身就是一个最大序列（全降序的），直接逆序就行了
        for (int p = j, q = n - 1; p < q; p++, q --) {
            int temp = nums[p];
            nums[p] = nums[q];
            nums[q] = temp;
        }
    }

}
